package com.Questions.DP;


/**
 * 最长回文子序列
 */
public class leetcode516 {
    // 相比于最长回文子串 最长回文子序列需要在两个字符相等的时候
    // 需要将长度加二 如果字符不相等 那么长度不变即可
    // 而最长回文子串 不相等直接得false 相等则延续上一个状态

    public int longestPalindromeSubseq(String s) {
        int n=s.length();
        int[][] dp=new int[n][n];
        for(int i=0;i<n;++i){
            dp[i][i]=1;
        }
        for(int L=2;L<=n;++L){
            for(int i=0;i<n;++i){
                int j=i+L-1;
                if(j>=n){
                    break;
                }
                if(s.charAt(i)!=s.charAt(j)){// i j不相等
                    if(j-i==1){
                        dp[i][j]=dp[i][i];
                    }else{// 如果两个字符不相等 一定要取二者的最大值
                        dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                    }
                }else{// i j 相等
                    if(j-i==1){
                        dp[i][j]=dp[i][i]+1;
                    }else{
                        dp[i][j]=dp[i+1][j-1]+2;
                    }
                }
            }
        }
        return dp[0][n-1];
    }
}
